//
// Created by wangbo on 9/22/18.
//
#include <iostream>
#include <stack>
#include <queue>
#include "ergodic.h"
using namespace std;
/*
 * 二叉树前序遍历的递归版本
 */

void ergodic::front_bianli(BTree root) {
    if(root==NULL) return ;
    cout<<root->val<<" ";
    front_bianli(root->left);
    front_bianli(root->right);
}

/*
 * 二叉树前序遍历的非递归版本
 *
 */
void ergodic::front_bianli1(BTree root) {
     stack<BTree > ss;
     ss.push(root);
     while(!ss.empty()){
         BTree top = ss.top();
         cout<<top->val<<" ";
         ss.pop();
         if(top->right != NULL) ss.push(top->right);
         if(top->left != NULL) ss.push(top->left);
     }
}

void ergodic::front_bianli2(BTree root) {
    if(root==NULL) return ;
    stack<BTree > ss;
    BTree pt = root;
    while(pt!=NULL ||!ss.empty())
    {
        if(pt!=NULL){
            cout<<pt->val<<" ";
            ss.push(pt);
            pt=pt->left;
        }else{
            pt  = ss.top();
            ss.pop();
            pt = pt->right;
        }
    }
}
void ergodic::inorder_traversal1(BTree root) {
/**
* @Description: 中序遍历的非递归
* @Param:
* @return:
* @Author: Mr.Wang
* @Date: 10/1/18
**/

    if(root == NULL ) return ;
    stack<BTree > tree;

    while (root!=NULL ||!tree.empty())
    {
        if(root!=NULL)
        {
            tree.push(root);
            root=root->left;

        }else
        {

            root = tree.top();
            tree.pop();
            cout<<root->val<<" ";
            root=root->right;

        }

    }

}


/*
 * 递归版中序遍历
 */
void ergodic::inorder_traversal(BTree root) {
    if (root ==NULL) return ;
    inorder_traversal(root->left);
    cout<<root->val<<" ";
    inorder_traversal(root->right);
}



BTree ergodic::make_a_tree(vector<int> &nums) {
    /**
    * @Description: 层序生成二叉树。
    * @Param:
    * @return:
    * @Author: Mr.Wang
    * @Date: 10/1/18
    **/


    int index = 0 ;
    BTree head = gen_head(nums, index);
    index++;
    queue<BTree > tree;
    if(head!=NULL)
    {
        tree.push(head);
    }
    while(!tree.empty())
    {
        BTree tem = tree.front();
        tree.pop();
        tem->left = gen_head(nums, index);
        index++;
        tem->right = gen_head(nums, index);
        index++;
        if(tem->left!=NULL)
        {
            tree.push(tem->left);
        }

        if(tem->right!=NULL)
        {
            tree.push(tem->right);
        }
    }

    return head ;

}



void ergodic::back_travelsal(BTree root) {

    /**
    * @Description: 二叉树的后序遍历的递归版本
    * @Param:
    * @return:
    * @Author: Mr.Wang
    * @Date: 10/1/18
    **/
    if(root == NULL ) return ;
    back_travelsal(root->left);
    back_travelsal(root->right);
    cout<<root->val<<" ";
}

void ergodic::back_travelsal1(BTree root) {
    /**
    * @Description:  二叉树的后序遍历非递归版本,使用两个栈空间
    * @Param:
    * @return:
    * @Author: Mr.Wang
    * @Date: 10/1/18
    **/
    if(root == NULL)return ;
    stack<BTree > tree1;
    stack<BTree > tree2;
    tree1.push(root);
    while (!tree1.empty())
    {
        BTree tem = tree1.top();

        tree1.pop();
        if(tem->left!=NULL)
        tree1.push(tem->left);
        if(tem->right!=NULL)
        tree1.push(tem->right);
        tree2.push(tem);
    }
    while (!tree2.empty())
    {
        BTree tem = tree2.top();
        tree2.pop();
        cout<<tem->val<<" ";
    }


}

void ergodic::sequence_traversal(BTree root) {

    /**
    * @Description: 二叉树的层序遍历
    * @Param:
    * @return:
    * @Author: Mr.Wang
    * @Date: 10/1/18
    **/
    if(root == NULL) return;
    queue<BTree >tree;
    tree.push(root);
    while (!tree.empty())
    {
        BTree tmp = tree.front();
        tree.pop();
        cout<<tmp->val<<" ";
        if(tmp->left!= NULL)tree.push(tmp->left);
        if(tmp->right!= NULL)tree.push(tmp->right);

    }


}


